package com.unionfind_01;

/**
 * @Author: tgy
 * @Date: 1/12/21 5:42 PM
 */
public class UF_QuickUnion_Rank extends UF_QuickUnion{

    private int[] ranks;

    public UF_QuickUnion_Rank(int size) {
        super(size);

        ranks = new int[size];

        for (int i = 0; i < size; i++) {

            ranks[i] = 1;
        }
    }

    @Override
    protected void justify(int p1, int p2) {

        if (ranks[p1] == ranks[p2]) {

            parents[p2] = p1;
            ranks[p1] += 1;
        }else if (ranks[p1] < ranks[p2]){

            parents[p1] = p2;
        }else {

            parents[p2] = p1;
        }
    }

    public static void main(String[] args) {

        UF_QuickUnion quickUnion = new UF_QuickUnion_Rank(9);


        quickUnion.union(1,3);
        quickUnion.union(2,8);
        quickUnion.union(4,7);
        quickUnion.union(3,4);
        quickUnion.union(1,2);

        System.out.println(quickUnion.isSame(1, 4));

    }

}
